//
// Created by bleedingfight on 2020/6/28.
//
#include "getDuplication.h"
int countRange(std::vector<int>&numbers,int start,int end){
    int count = 0;
    for(auto elem:numbers){
        if(elem>=start &&elem<=end)
            count++;
    }
    return count;
}
int getDuplication(std::vector<int>&numbers){
    int start = 1;
    int end = numbers.size()-1;
    while (start<end){
        int middle = (end-start)/2 +start;
        int left_count = countRange(numbers,start,middle);
        int right_count = countRange(numbers,middle+1,end);
        if(left_count>middle-start+1){
            end = middle;
        }else{
            start = middle+1;
        }
    }
    return start;
}
